/*
 * @lc app=leetcode.cn id=1049 lang=typescript
 *
 * [1049] 最后一块石头的重量 II
 */

// @lc code=start
function lastStoneWeightII(stones: number[]): number {
  const n = stones.length;

  let sum = 0;
  for (const stone of stones) {
    sum += stone;
  }

  // 我们需要找的就是最接近数组元素总和一半的值
  let target = (sum / 2) >> 0;
  const dp: number[][] = new Array(n + 1).fill(0).map(() => new Array(target + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    const stone = stones[i - 1];
    for (let j = 0; j <= target; j++) {
      dp[i][j] = dp[i - 1][j];
      if (j >= stone) {
        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - stone] + stone);
      }
    }
  }
  return sum - dp[n][target] * 2;
}
// @lc code=end
